package 贪心算法;

import java.util.Arrays;
import java.util.Comparator;

public class 用最少数量的箭引爆气球_452 {
    public int findMinArrowShots(int[][] points) {

        if (points.length == 0) {
            return 0;
        }
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            //按照end升序排列
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[1],o2[1]);//防止溢出
            }
        });
        //至少有一个区间不相交,就是只有一个区间的时候
        int count = 1;
        //排序后第一个区间就是x
        int x_end = points[0][1];

        for (int[] interval : points) {
            int start = interval[0];
            if (start > x_end) {
                //找到下一个选择的区间了
                count++;
                x_end = interval[1];
            }
        }
        return count;

    }
}
